package 并查集;

import 抽象数据类型.UF;

/**
 * @description:
 * @author: ywk
 * @date: 2021-01-20
 */
public class 围棋 {
    static void solve(char[][] board) {
        if (board.length == 0) return;
        int m = board.length;
        int n = board[0].length;
        // 给 dummy 留⼀个额外位置
        UF uf = new UF(m * n + 1);
        int dummy = m * n;
        // 将⾸列和末列的 O 与 dummy 连通
        for (int i = 0; i < m; i++) {
            if (board[i][0] == 'O') uf.union(i * n, dummy);
            if (board[i][n - 1] == 'O') uf.union(i * n + n - 1, dummy);
        }
        // 将⾸⾏和末⾏的 O 与 dummy 连通
        for (int j = 0; j < n; j++) {
            if (board[0][j] == 'O') uf.union(j, dummy);
            if (board[m - 1][j] == 'O') uf.union(n * (m - 1) + j, dummy);
        }
        // ⽅向数组 d 是上下左右搜索的常⽤⼿法
        int[][] d = new int[][]{{1, 0}, {0, 1}, {0, -1}, {-1, 0}};
        for (int i = 1; i < m - 1; i++)
            for (int j = 1; j < n - 1; j++)
                if (board[i][j] == 'O')
                    // 将此 O 与上下左右的 O 连通
                    for (int k = 0; k < 4; k++) {
                        int x = i + d[k][0];
                        int y = j + d[k][1];
                        if (board[x][y] == 'O') uf.union(x * n + y, i * n + j);
                    }
        // 所有不和 dummy 连通的 O，都要被替换
        for (int i = 1; i < m - 1; i++)
            for (int j = 1; j < n - 1; j++)
                if (!uf.connected(dummy, i * n + j)) board[i][j] = 'X';
    }

    public static void main(String[] args) {
        solve(new char[][]{
                {'O', '1', '1', '1'},
                {'O', '1', 'O', '1'},
                {'O', '1', 'O', '1'},
                {'O', '1', '1', '1'}
        });
    }
}